The invention relates generally to navigating within large hyperbolic space and more particularly to methods and systems for reducing the display cluttering and complexity of navigating within large hierarchies such as organizational charts or Internet resources.
Recently, there has been substantial research focused on visual mining of large hierarchies of nodes, such as the World Wide Web structure, organization charts, and file systems, using a hyperbolic tree space. For example, in Web data mining, there is an immediate need for users to visualize the content and usage of the Web. How to navigate through millions of documents to access information on one display is a problem which needs to be solved. Hyperbolic space provides an elegant solution to displaying large hierarchies on a user screen. Hyperbolic space is different from the conventional approaches of laying trees on an Euclidean space. In Euclidean space, the area of a circle which contains nodes grows linearly. In hyperbolic spaces, the area of a circle grows exponentially with respect to its radius. As a result, known approaches using hyperbolic space can handle a graph of over 20,000 documents on the Web, using a focus-and-context scheme.
Hyperbolic space allows a user to navigate through the nodes of a large hierarchy and to view the relationship of the visible portion of the space to the entire structure on a single display. This is an improvement over techniques in which multiple displays are required to represent a large amount of data sets, with the user having to click through display after display in order to find the information that is needed.
In a directed hierarchical hyperbolic tree, nodes are organized along parent and child relationships. A parent can have many children. A child can have only one parent. For example, in an organization chart hyperbolic tree, each employee reports to one manager. A manager may have many employees. However, in practice this may not be sufficient, since an employee may report to two managers (e.g., one regular manager and one temporary project manager). Thus, two paths may be needed, one for the regular manager and the other for the temporary project manager.
In a customer support application, a hyperbolic tree may be used to organize large numbers of questions and answers in a hierarchical structure. Questions are parent nodes, while answers are arcs (pointers) to child nodes. A question can have several answers. An answer can lead to more questions and answers. However, it is sometimes necessary for an answer to link to another question-and-answer group (sub-tree) which does not directly belong to the hierarchical hyperbolic space.
In a directed non-cyclic hierarchical hyperbolic space, a node (except for a root node) has exactly one primary parent. If a node has more than one parent, then exactly one is designated as the xe2x80x9cprimary parentxe2x80x9d and the others are referred to as xe2x80x9csecondary parents.xe2x80x9d The link from a node""s secondary parent to the node is referred to as a xe2x80x9csecondary path.xe2x80x9d The path from a node""s primary parent to the node is referred to as the xe2x80x9cprimary path.xe2x80x9d For example, the path to the regular manager is a direct hierarchical link, called the primary path. The path to the temporary project manager is a directed non-hierarchical link, called the secondary path. A node which serves as a multi-path node contains both the primary path and the secondary path.
In the above examples, a secondary path is needed to represent the relationship between the employee and the employee""s temporary project manager or to relate a particular answer with other question-and-answer groups. A concern is that strict hierarchical tree structures are too restrictive, since often a relationship needs to link different branches of the tree. Commercially available hyperbolic tree implementations do not support such secondary paths. One solution would be to depict the secondary relationships with additional lines. However, this solution could introduce thousands of lines and intersections, as will be explained with reference to FIG. 1, which includes only primary relationships, and FIG. 2, which includes both primary and secondary relationships. Also, for far away nodes that are off the screen, it would introduce xe2x80x9cbrokenxe2x80x9d lines that do not terminate in a node on the current display. As a result, the hyperbolic space becomes very cluttered and difficult to visualize.
With reference to FIG. 1, a conventional tree structure 10 is shown as having a root node 12 that is labeled xe2x80x9cMS PRODUCTS.xe2x80x9d The root node includes eight child nodes 14, 16, 18, 20, 22, 24, 26 and 28 that are connected to the parent node by edges (i.e., primary paths) 30, 32, 34, 36, 38, 40, 42 and 44, respectively. Each of the child nodes is the parent node to at least one other node. For example, the child node 20 labeled xe2x80x9cOFFICE PRODUCTSxe2x80x9d is the parent node for six other nodes 46, 48, 50, 52, 54 and 56 that are connected to the node 20 by primary paths. In the hyperbolic space, the far away nodes and edges are diminished when the user is not focusing on them. These nodes will reappear when the user warps the display to focus on or near them. The user can dynamically warp the display to focus on thousands of different nodes for navigation. The conventional tree of FIG. 1 is a non-cyclic hierarchical hyperbolic structure without secondary paths. Thus, the structure will include n nodes and nxe2x88x921 edges.
FIG. 2 is an illustration of the same tree, but with secondary paths in addition to the primary paths. The multi-path hyperbolic tree includes numerous lines and intersections. There are also many broken lines. As can be seen, the hyperbolic tree becomes very cluttered. The cluttering is increased if additional secondary paths are necessary in order to show all of the relationships. In the illustration of FIG. 2, there are n nodes, nxe2x88x921 primary edges and numerous secondary edges and intersections.
What is needed is a system and method for visualizing and navigating through a complex hyperbolic space with multiple paths, such as a web-based hyperbolic space, while preserving the simplicity of nodes organized along parent and child relationships.
A system and a method in accordance with the invention utilize hidden links, mapping, and unmapping to enable single-screen visualization of a directed non-cyclic hyperbolic space with multiple path links. The hidden links technique hides all of the secondary paths in each node""s property at the time that the hyperbolic space is initialized. The nodes to which a secondary path are pointed become accessible and interactive via the secondary path only at the time of focus upon portions of the hyperbolic space related to the secondary path. The user can easily navigate through all possible paths without tracing many lines and intersections.
In the preferred embodiment, the hyperbolic space is organized in a directed non-cyclic hierarchical space. Thus, there is a primary graph which links all of the nodes in a tree form that follows the one parent per child convention. These links are primary tree links. However, there are also secondary links that define a highly connected graph. A node in the hierarchy can have one incoming primary link (i.e., one link from a primary parent node) and may have many secondary links. The secondary paths are hidden at the time that the hyperbolic space is initialized.
A xe2x80x9cprimary pathxe2x80x9d is defined herein as a tree link. Preferably, it is a directed non-cyclic graphic link in a hierarchical hyperbolic space. With the exception of a root node, each node has one primary parent, with the link from a node""s primary parent to that node being the primary path. A xe2x80x9csecondary pathxe2x80x9d is defined as a link in which additional (i.e., secondary) parents are defined. The link from a node""s secondary parent to that node is a secondary path. A xe2x80x9chidden-link nodexe2x80x9d (as referred to as a xe2x80x9cmulti-path nodexe2x80x9d) is defined as a node that contains both primary and secondary paths. xe2x80x9cPrimary sub-tree nodesxe2x80x9d (also referred to as xe2x80x9cprimary sub-space nodesxe2x80x9d) are used herein to define the relationship between a sub-space parent node and its child nodes linked to the tree by a primary path. xe2x80x9cSecondary sub-tree nodesxe2x80x9d (also referred to as xe2x80x9csecondary sub-space nodesxe2x80x9d) are used herein to define a relationship between a sub-space parent node and its child nodes linked to the tree by a secondary path.
A multi-path processor is used to manage three basic processing elements. As a first element, a multi-path property is added in each child node to indicate whether the node has at least one secondary path in addition to its primary path. As a second element, an examiner checks each child node""s multi-path property when a user focuses on the node. If a node has at least one secondary path, the multi-path processor invokes the concurrent actions, such as mapping and unmapping. The third processing element is the mapper/unmapper which simultaneously maps and unmaps the secondary sub-tree nodes. Following the navigation of a secondary path, the multi-path processor reverses the operations, unmapping the sub-tree nodes and restoring the node to the original structure.
By operation of the multi-path processor, five different states are defined during navigation that includes a secondary path. In an idle state, the hyperbolic space with multi-path links has the same layout as it would have without the multi-paths. That is, the secondary paths are transparent to the user, so that there are no extra lines and intersections within the graph. An activate state is triggered by identification of a multi-path node by a user. Preferably, the multi-path nodes are visually distinguishable from nodes which do not include secondary paths. When the user identifies a particular multi-path node, one or more temporary secondary path nodes will be drawn from that node. The user can dynamically select one of the secondary path nodes for further navigation.
The third state is a map/unmap state (i.e., move state). The processor uses parallel mapping and unmapping methods to move the selected secondary sub-tree nodes from their original position in the tree structure to a position that reflects the relationship with the identified multi-path node. Thus, a new hyperbolic space is created. The mapping and unmapping operations are concurrently executed, with a navigation state being enabled only after both operations are completed. In a navigation state, the mapped secondary sub-tree nodes are browsed and navigated in a simplified hyperbolic space. Finally, at the end of the navigation of the secondary sub-tree nodes, the sub-tree nodes are returned to their original positions within the tree structure. The reset state may be triggered by departure of a user from further navigation of the secondary sub-tree (i.e., an xe2x80x9cunfocusxe2x80x9d on the secondary sub-tree) or by the user pressing a reset button.